JSAI2026 構造類似度に基づくクラスタリングを用いた進化的学習による複合的区間グラフパターンの獲得
テーマ
グラフ構造データからの機械学習
区間グラフデータから、正例に多く当たり負例に当たりにくい特徴的なグラフパターンを獲得する研究
単一パターンではなく、複数パターンの集合として特徴を表す「複合的区間グラフパターン」を扱う
背景課題
区間グラフは、時間・資源・区間の重なり関係を表すのに向いている
バイトのシフトの重なりもグラフで表現できる
区間グラフ知らなかった daiiz.icon
座長も初めて聞いたと言っていた。なるほど。
既存手法では、1つの区間グラフパターンを進化的学習で獲得していた
しかし正例が複数の構造タイプを含む場合、単一パターンだけでは分類性能が不足しやすい
区間グラフ
区間グラフパターン
単体頂点のいくつかの変数でラベルづけされた、区間グラフの構造をしたグラフパターン
？？daiiz.icon
提案
正例の区間グラフを、構造類似度に基づいてクラスタリングする
各クラスタごとに、遺伝的プログラミングで区間グラフパターンを獲得する
得られた複数の区間グラフパターンをまとめて、1つの複合的パターンとして扱う
ポイント
区間グラフはPQ木で表現できる
PQ木の全体構造・局所構造から特徴量を作り、k-meansで正例をクラスタリングする
サブルーチン: PQ 木パターンを個体として交叉・逆位・突然変異を行う
メインルーチン: 各クラスタで得たパターン列を複合的パターンとして評価
実験環境
macOS メモリ16GB
手元でも試せそうだ daiiz.icon
評価方法
人工データを用意
3つの区間グラフパターンからなる正解用の複合パターン
それにマッチするデータを正例、マッチしないデータを負例として生成
正例1000件、負例1000件で評価
感想 daiiz.icon
区間グラフ、表現技術として強力な気がする
ついていけなかったので勉強した方がよい
#聴講メモ